//int BinaryTreeSize(struct TreeNode* root)
//{
//    if (root == NULL)
//        return 0;
//    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
//}
//
//void _preorderTraversal(struct TreeNode* root, int* a, int* pi)
//{
//    if (root == NULL)
//        return;
//    a[(*pi)++] = root->val;
//    _preorderTraversal(root->left, a, pi);
//    _preorderTraversal(root->right, a, pi);
//
//
//}


//struct TreeNode* invertTree(struct TreeNode* root) {
//    if (root == NULL)
//        return NULL;
//    struct TreeNode* left = invertTree(root->left);
//    struct TreeNode* right = invertTree(root->right);
//    root->left = right;
//    root->right = left;
//    return root;
//}


//
//bool _isSymmtric(struct TreeNode* leftNode, struct TreeNode* rightNode)
//{
//    if (leftNode == NULL && rightNode == NULL)
//        return true;
//    if (leftNode == NULL || rightNode == NULL)
//        return false;
//    if (leftNode->val != rightNode->val)
//        return false;
//    return _isSymmtric(leftNode->left, rightNode->right)
//        && _isSymmtric(leftNode->right, rightNode->left);
//}
//
//bool isSymmetric(struct TreeNode* root) {
//    return _isSymmtric(root->left, root->right);
//}




//bool isSameTree(struct TreeNode* p, struct TreeNode* q)
//{
//    if (p == NULL && q == NULL)
//        return true;
//    if (p == NULL || q == NULL)
//        return false;
//    if (p->val != q->val)
//        return false;
//    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//}
//
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
//    if (root == NULL)
//        return false;
//    if (isSameTree(root, subRoot))
//        return true;
//    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//}




//typedef char BTDataType;
//typedef struct BinaryTreeNoode
//{
//    BTDataType data;
//    struct BinaryTreeNoode* left;
//    struct BinaryTreeNoode* right;
//}BTNode;
//
//
//BTNode* BuyNode(BTDataType x)
//{
//    BTNode* Node = (BTNode*)malloc(sizeof(BTNode));
//    Node->data = x;
//    Node->left = NULL;
//    Node->right = NULL;
//    return Node;
//}
//
//
//BTNode* CreaterBinaryTree(char* a, int* pi)
//{
//    if (a[*pi] == '#')
//    {
//        (*pi)++;
//        return NULL;
//    }
//
//
//    BTNode* root = BuyNode(a[*pi]);
//    (*pi)++;
//
//
//    root->left = CreaterBinaryTree(a, pi);
//    root->right = CreaterBinaryTree(a, pi);
//    return root;
//}
//
//
//void InOrder(BTNode* root)
//{
//    if (root == NULL)
//        return;
//    InOrder(root->left);
//    printf("%c ", root->data);
//    InOrder(root->right);
//}
//
//
//int main() {
//    char str[101];
//    scanf("%s", str);
//    int i = 0;
//    BTNode* root = CreaterBinaryTree(str, &i);
//    InOrder(root);
//    printf("\n");
//    return 0;
//}



int BTreeHeight(struct TreeNode* root)
{
    if (root == NULL)
        return 0;
    int leftHeight = BTreeHeight(root->left);
    int rightHeight = BTreeHeight(root->right);
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}


bool isBalanced(struct TreeNode* root) {
    if (root == NULL)
        return true;
    int gap = fabs(BTreeHeight(root->left) - BTreeHeight(root->right));
    if (gap > 1)
        return false;
    return isBalanced(root->left) && isBalanced(root->right);
}